package leetcode100;

// TODO 动态规划 | 状态转移方程 [经典] 【-】 打家劫舍
// TODO https://leetcode.cn/problems/house-robber/solutions/263856/da-jia-jie-she-by-leetcode-solution/
// TODO 状态转移方程: dp[i]=max(dp[i−2]+nums[i],dp[i−1])

public class lc100_0198 {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }

        // 定义状态数组
        int[] dp = new int[n];
        // 定义初始状态
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            // 状态转移方程
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[n - 1];
    }
}